package zuochengyun.chapter5;

//回文最少分割数
public class MinPalidromeCount {

	public int minCut(String str){
		if(str == null || str.equals("")){
			return 0;
		}
		char[] chars = str.toCharArray();
		int len = chars.length;
		//dp[i]表示以chars[i...len - 1]的最少分割数
		int[] dp = new int[len + 1];
		dp[len] = -1;
		//用于判断chars[i...j]是否是回文串
		boolean[][] palidrome = new boolean[len][len];
		for (int i = len - 1; i >= 0; i--) {
			dp[i] = Integer.MAX_VALUE;
			for (int j = i; j < len; j++) {
				//对于palidrome[i][j]来说，palidrome[i + 1][j - 1]已知
				//palidrome[i][j]为true，那么一定是以下三种情况
				//1. chars[i..j]只有一个字符
				//2. chars[i..j]只有两个字符且两个字符相等
				//3. chars[i + 1 ... j - 1]是回文，并且 chars[i] == chars[j]
				
				//如果chars[i...j]为回文串，那么dp[i]就取dp[i]和dp[j + 1] + 1(chars[i..j]分为独立的一个回文串)的最小值
				if(chars[i] == chars[j] && ( j - i < 2 || palidrome[i + 1][j - 1])){
					palidrome[i][j] = true;
					dp[i] = Math.min(dp[i], dp[j + 1] + 1);
				}
				
			}
		}
		return dp[0];
	}
}
